#include "junix.h"


template<
typename ValueType,
typename Cmp
> 
class BST;

template<typename ValueType=int>
struct Node {
	Node() : parent(0),left(0),right(0) { }
	Node(const ValueType& value) 
		: data(value),parent(0),left(0),right(0) { }

	ValueType data;
	Node<ValueType> *parent,*left,*right;
};

template<
typename ValueType=int,
typename Cmp=std::less<ValueType> 
>
class BST {
	public:
		BST() : root(0) { }
		~BST() { delete root; }

		void build_BST(ValueType vec[], const int size) {
			for (int i=0;i<size;i++) {
				add_node(vec[i]);
			}
		}

		void inorder_tree_walk() const {
			inorder_tree_walk(root);
		}

		Node<ValueType>* binary_search(const ValueType& value) const {
			Node<ValueType> *p=root;
			Cmp cmp;

			while (p) {
				if (value == p->data) return p;

				if (cmp(value,p->data)) {
					p = p->left;
				} else {
					p = p->right;
				}
			}

			return p;
		}


		void add_node(const ValueType& value) {
			Node<ValueType> *n = new Node<ValueType>(value);
			Node<ValueType> *p=0, *q=root;
			Cmp cmp;

			while (q) {
				p = q;
				if ( cmp(n->data,q->data) ) {
					q = q->left;
				} else {
					q = q->right;
				}
			}

			n->parent = p;
			if (!p) {
				root = n;
			} else {
				if ( cmp(n->data,p->data) ) {
					p->left = n;
				} else {
					p->right = n;
				}
			}
		}


		void inorder_tree_walk(Node<ValueType> *x) const {
			if (x) {
				inorder_tree_walk(x->left);
				std::cout<<x->data<<std::endl;
				inorder_tree_walk(x->right);
			}
		}

		//minimum node
		Node<ValueType>* minimum(Node<ValueType> *x) {
			Node<ValueType> *p=x;
			while (p) {
				p = p->left;
			}

			return p;
		}

		//maximum
		Node<ValueType>* maximum(Node<ValueType> *x) {
			Node<ValueType> *p=x;
			while (p) {
				p = p->right;
			}

			return p;
		}

		//successor
		Node<ValueType>* successor(Node<ValueType> *x) {
			if (x->right) return minimum(x->right);

			Node<ValueType> *y=x->parent;
			while (y && x==y->right) {
				x = y;
				y = x->parent;
			}

			return y;
		}

	public:
		Node<ValueType> *root;
};

int main(int argc, char **argv)
{
	const int size = 10000;
	std::vector<int> V(size);
	using boost::bind;
	std::generate(V.begin(),V.end(),
			bind(std::modulus<int>(), bind(rand), size));
	BST<int,std::less<int> > bst;
	bst.build_BST(&V[0],V.size());

	bst.inorder_tree_walk();
}
